package br.cns.metrics;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import br.cns.Metric;
import br.cns.TMetric;

public class VertexBetweenness implements Metric {
	private static final VertexBetweenness instance = new VertexBetweenness();
	
	private VertexBetweenness() {
	}
	
	public static VertexBetweenness getInstance() {
		return instance;
	}
	
	public double calculate(int[][] matrix) {
		// TODO Auto-generated method stub
		return 0;
	}
	
	private double[] vertexBetweenness(int[][] matrix) {
		int totalVertexes = matrix.length;
		int v = 0;
		double[] betweenness = new double[totalVertexes];
		double[] delta = new double[totalVertexes];
		int[] d = new int[totalVertexes];
		int[] sigma = new int[totalVertexes];
		List<LinkedList<Integer>> P;
		Stack<Integer> S;
		Queue<Integer> Q;
		
		for (int i = 0; i < totalVertexes; i++) {
			betweenness[i] = 0.0;
		}
		
		for (int s = 0; s < totalVertexes; s++) {
			for (int i = 0; i < totalVertexes; i++) {
				d[i] = -1;
				sigma[i] = 0;
			}
			
			d[s] = 0;
			sigma[s] = 1;
			
			P = new ArrayList<LinkedList<Integer>>(totalVertexes);
			S = new Stack<Integer>();
			Q = new LinkedList<Integer>();
			
			for (int i = 0; i < totalVertexes; i++) {
				P.add(new LinkedList<Integer>());
			}
			
			Q.add(s);
			
			while (!Q.isEmpty()) {
				v = Q.poll();
				S.push(v);
				
				for (int w = 0; w < totalVertexes; w++) {
					if (matrix[w][v] == 0) {
						continue;
					}
										
					if (d[w] < 0) {
						Q.add(w);
						d[w] = d[v] + 1;
					} 
					
					if (d[w] == d[v] + 1) {
						sigma[w] += sigma[v];
						P.get(w).add(v);
					}
				}
			}
			
			for (int i = 0; i < totalVertexes; i++) {
				delta[i] = 0.0;
			}
			
			while (!S.isEmpty()) {
				int k = S.pop();
				LinkedList<Integer> predecessors = P.get(k);
				
				for (int j : predecessors) {
					delta[j] += (((double)sigma[j]/(double)sigma[k]) * (1 + delta[k]));
				}
				
				if (k != s) {
					betweenness[k] += delta[k]/2.0;
				}				
			}
		}
		
		return betweenness;
	}

	@Override
	public String name() {
		//TODO Adicionar a classe no enum TMetric
		return "";
	}

	public static void main(String[] args) {
		int[][] m = new int[][] {
				{0, 1, 1, 0, 0, 0},
				{1, 0, 0, 1, 0, 0},
				{1, 0, 0, 1, 0, 0},
				{0, 1, 1, 0, 1, 1},
				{0, 0, 0, 1, 0, 1},
				{0, 0, 0, 1, 1, 0}};
		VertexBetweenness vb = new VertexBetweenness();
		double[] b = vb.vertexBetweenness(m);
		
		for (int i = 0; i < b.length; i++) {
			System.out.printf("v[%d] = %f\n", i+1,b[i]);
		}
	}
}
